As a prior art regarding a method of calculating, when inputs for a given function are dispersed and held in a plurality of devices, an output of this function while these devices are working together, a method is proposed by Beaver, Micali, and Rogaway in paper “D. Beaver, S. Micali, and P. Rogaway, ‘The round complexity of secure protocols’, Annual ACM Symposium on Theory of Computing 22, pages 503-513, 1990”. This paper is hereinafter referred to as Non-patent Document 1.
The technology disclosed in Non-patent Document 1 relates to a method of calculating, when the number of calculators uα who are connected to one another via a network is λ, each of the calculators has a secret input xα, and an arbitrary function g is given, an output g(x1, . . . , λ) while the calculators work together, wherein the secret of each of the calculators is not leaked beyond g(x1, . . . , xλ) and the number of times for performing communication necessary for the calculation with is a fixed number. The technology disclosed in Non-patent Document 1 will be described with reference to FIGS. 1, 2 and 19.
[Garbled Circuit]
[Syntax]
A circuit f includes m logic gates. Each gate is denoted by symbols G1, . . . , Gl, . . . , Gm. As shown in FIG. 19, each gate has two inputs and one output. Each output may be input to a plurality of gates. An output line of Gk is generally input to a plurality of gates but all signals flowing through the line have the same value of 0 or 1. Then, all line output from the gate Gk are referred to as wk. The number of line input to the circuit f is n, which is expressed as follows.
{wk}k=m+1, . . . , m+n. Then, w1, . . . , wl denote the output of the circuit f.
The number of calculators is λ, and a set of the calculators is expressed as follows.{u(α)}α=1, . . . ,λ
The number of bits input by u(α) to the circuit f is Iα.
With respect to (Σα=1λIα=λ). k=m+1, . . . , m+n where the sum of those bits is set as n, a bit input to each wk is represented by bk, and each of the bits is allocated to u(α) by the number of Iα in the following manner. That is, u(α) determines the following set{bkε{0,1}}k=m+Σ⊖=1α−1Iβ+1, . . . ,m+Σβ=1αIβ
When outputs of the gates Gi and Gj are input to the gate Gk, a relation between the output bj of Gj and the output bk of Gk is represented as follows.bk=bi⊚G[k]bjThen, □ denotes exclusive OR of the bit and • denotes a character string sequences.
t denotes a safety variable, and G, H, and F denote pseudorandom number generating devices for output character strings of tλ bits.
[Construction]
A protocol is roughly divided into three processes which are (1) an input process 402, (2) a parallel construction process 400 of a garbled circuit based on a calculation performed by a large number of people, and (3) a result output process 401 for performing an input disclosure and a circuit calculation.
The input process 402 is performed in the following manner. Information on a circuit for performing the calculation, information on another calculator, and input data of each device are input to each device.
The parallel construction process 400 of the garbled circuit is performed in the following manner. In a procedure of this process, as shown in FIG. 2, a phase 502 in which λ computers 501 individually performs the calculation and a phase 503 in which all the computers perform communication with one another are alternately performed. Then, the number of performing the repetition is set as a fixed number 504, and whatever function is desired to be calculated, the following process can be completed. Also, in each communication phase, each of the computers transmits data to all of the other computers. In order to generate the data transmitted at this time, transmission data of other computers in the same communication phase of this transmission should not be needed. That is, when there is a transmission which should wait for data of other computers, the communication phase in which this transmission is performed is counted as a different communication phase from the communication phase in which data is waited for.
[1] In cooperation with one another, the calculators uniquely and randomly generate a set of character strings of bits and a set of bits so that these sets are secretly dispersed to all the calculators.{sαk′sαkεR{0,1}t}k=1, . . . ,m+n;α=1, . . . ,λ{ρkεR{0,1)}}Wherein
Sk:=sk1·sk2· . . . skλ
S′k:=s′k1·s′k2· . . . s′kλ.
Regarding {Sk},{ρk}, if λk□bk=0, in the calculation phase of the circuit, Sk is made public, and if λk□bk=1, S′k is made public.
[2] For each of the calculators uα, the following data is revealed.{sαk}k=1, . . . ,m+n 
[3] With respect to k=1, . . . , m+n, each of the calculators uα calculates the following character strings of tλ bits.gαk=G(sαk)g′αk=G(s′αk)hαk=H(sαk)h′αk=H(s′αk)fαk=F(sαk)f′αk=F(s′αk)
Then, each of the calculators uα commits the following data to prove to the other calculators that these values are calculated correctly.{gαk′,g′αk′,hαk′,h′αk′,fαk′,f′αk′}k
[4] With respect to k=1, . . . , m+n, the calculators secretly perform the following calculation in a dispersed manner.σk1· . . . σkλ=Sk if λk□bk=0σk1· . . . σkλ=S′k if λk□bk=1
[5] In cooperation with one another, with respect to k=1, . . . , m+n, the calculators secretly perform the following calculation in a dispersed manner.Ak=gl1□ . . . □glλ□gl1□ . . . □gjλ□Sk if ρl⊚G[k]ρj=ρk Ak=gl1□ . . . □glλ□gl1□ . . . □gjλ□S′k if ρl⊚G[k]ρj≠ρk Bk=hl1□ . . . □hlλ□g′j1□ . . . □g′jλ□Sk if ρl⊚G[k]ρl=ρk Bk=hl1□ . . . □hlλ□g′j1□ . . . □g′jλ□S′k if ρl⊚G[k]ρ′l≠ρk Ck=g′l1□ . . . □g′lλ□hj1□ . . . □hjk□Sk if ρ′j⊚G[k]ρl=ρk Ck=g′l1□ . . . □g′lλ□hj1□ . . . □hjλ□S′k if ρ′l⊚G[k]ρl≠ρk Dk=h′l1□ . . . □h′lλ□g′j1□ . . . □g′jλ□Sk if ρ′l⊚G[k]ρ′j=ρk Dk=h′l1□ . . . □h′lλ□g′j1□ . . . □g′jλ□S′k if ρ′l⊚G[k]ρ′j≠ρk 
It should be noted that a signal input to the gate Gk is outputs of the gate Gl and the gate Gj. This state is shown in FIG. 19. The disclosure of the input and the generation of the circuit in the result output process 401 are performed as follows.
[1] The calculators reveal the following data.{ρk}k=1, . . . ,l {fkα}k=1, . . . ,m+n;α=1, . . . ,λ{σk1• . . . •σkλ}k=1, . . . ,m+n {Ak,Bk,Ck,Dk}}k=1, . . . ,m+n 
[2] With respect to k=1, . . . , m+n, in an order from k which is closer to the input of the circuit, from Si or S′l, and Sj or S′j, S*k is obtained as follows. This refers to Sk or S′k.
Sk*=Ak□gl1□ . . . □glλ□gl1□ . . . □gjλ if Sl,Sj are processed
Sk*=Bk□hl1□ . . . □hlλ□g′j1□ . . . □g′jλ if Sl,Sj, are processed
Sk*=Ck□g′l1□ . . . □g′lλ□hj1□ . . . □hjλ if S′l, S′j are processed
Sk*=Dk□h′l1□ . . . □h′lλ□g′l1□ . . . □g′jλ if S′i,S′j, are processed
[3] With respect to all of α=1, . . . , λ; k=1, . . . , m+n, by checking the following, S*k=Sk or S*k=S′k is confirmed.fake=F(sαk),f′a=F(s′ak)
[4] With respect to k=1, . . . , m+n, when all the calculators obtain Sk, ρk+bk=0 is established, and when all the calculators obtain S′k, ρk+bk=1 is established, thereby finding out bk.
As other prior art for such a method as described in the section of Technical Field, there is a method proposed by Ishai and Kushilevitz in paper “Y. Ishai and E. Kushilevitz, ‘Randomizing Polynomials: A new Representation with Applications to Round-Efficient Secure Computation’, IEEE Symposium on Foundations of Computer Science 2000, pages 294-304”. Hereafter, this paper is referred to as Non-patent Document 2. The prior art of Non-patent Document 2 will be described with reference to FIGS. 3 and 4.
[Randomizing Polynomial]
Non-patent Document 2 proposes a method of expressing a given function by a low order polynomial on the finite field. In particular, Non-patent Document 2 demonstrates that an arbitrary function can be expressed by a third polynomial. Evaluation of a low order polynomial can be performed by performing a round by a fixed number of times. In general, the function can be expressed in various forms such as a circuit.
A blanching problem described next can be expressed by a general function. A blanching problem BP=(G, φ, s, t) is referred to a mod-p blanching problem. G=(V, E) is a directed graph. φ is a labeling function for labeling one of 1, x1l, and the negation x0i to each of the sides. Then, s and t are special apexes.
When an input x=(x1, . . . , xn) is given, from the labeling function φ, a partial graph Gx of G is given. A value of a Boolean function f calculated by is f(x)=0 when a remainder obtained through division of the number of routes connecting s with t in Gx by p is 0, and otherwise the value is f(x)=1. The magnitude of BP is set as the number of the apexes of G.
The magnitude of BP is set as I. When a I\timesI adjacency matrix of the partial graph Gx is expressed as Hx, the number of routes connecting s-t is obtained as follows.(I+Hx+Hx2+·s)st=((1−Hx)−1)st mod p=detMx/det(I−Hx)} mod pWherein Mx is a matrix obtained by excluding a row s and a column t from the matrix (I−Hx). Therefore, the following data is found out.f(x)=0rank (Mx)=I−1f(x)=0rank (Mx)=I
Then, Mx includes an at most first order component with respect to x.
[Calculation Method]
A method of obtaining f(x) by using the randomizing polynomial method when the Boolean function f is given and the input is distributed to a plurality of calculators.
As shown in FIG. 3,
[1] Information on a function to be calculated, information on another calculator, and input data of each device are input to each device (605).
[2] BP is constructed which corresponds to f (600).
[3] The following processes are performed in parallel by the sufficient number of times.
[Process]
As shown in FIG. 4,
All the calculators disperse each component to uniquely and randomly generate I×I matrices R1, R2 (603) for calculating R1MxR2 which is a product of three matrices R1, Mx, R2 (604).
Each component is an at most third expression of components of R1, R2, x.
[4] From all the values of rankR1MxR2, it is presumed whether or not rank of Mx is I. When the probability that rank of Mx is I is high, 1 is output, and otherwise 0 is output (602).
In the above-mentioned method, when rank (Mx)=rank (M′x), distributions of R1MxR2 and R1M′xR2 become the same, a new matter is not leaked other than f(x) with respect to x.
Furthermore, when rank (Mx)=I with respect to any I, the probability of rank (R1MxR2)=I is larger than 0.08. Thus, the number of times for performing the process of Item 2 does not rely on I.
[Calculation Amount and Communication Amount]
In the method using the garbled circuit, the calculation with respect to each gate is individually performed, and the entire calculation amount and communication amount are proportional to the number of gates. t-n threshold dispersion (proportional to 2t2. The calculation in the t-n threshold dispersion refers to a calculation method in which the secret is dispersed to n calculators. Among the calculators, unless t calculators gather the data which each of them knows by itself, it is impossible to find out the dispersed secret or meaningful data in the middle of the calculation.
In the method using the randomizing polynomial, in the case where the t-n threshold dispersion is performed, the round number becomes 2(3) in proportion to t2 and the square of the magnitude of BP.
The communication amount and calculation amount in the randomizing polynomial method are proportional to the at most first order of the number of gates. Moreover, a coefficient of the highest order is substantially lower than that of the randomizing polynomial method and therefore efficient.
However, here, particular attention is paid to the case where t>n/2 is satisfied in the t−n threshold dispersion and a third party demands the verification of the calculation validity. In such a case, it is obviously applicable to extend the above-mentioned method. The result of the extension shows that the entire communication amount and calculation amount in the method using the garbled circuit are proportional to the number of gates and t3. When method using the randomizing polynomial is used, the communication amount and calculation amount are proportional to 1.5-th power of the number of gates. When the number of gates is larger, the method is not efficient.
A first problem resides in that the method of Non-patent Document 1 requires an enormous calculation amount of each calculator and an enormous calculation amount of a verifier who verifies the calculation validity.
This is because as each calculator needs to calculate the output of the pseudorandom number generating device, it is necessary to prove the calculation correctness while the calculation result is hidden.
A second problem resides in that the method of Non-patent Document 2 also requires an enormous calculation amount of each calculator and an enormous calculation amount of the verifier who verifies the calculation validity.
This is because the calculation amount performed by each calculator is in proportion to 1.5-th power of the number of gates in the case of expressing the function by the circuit and often the number of gates is extremely large. Thus the entire calculation amount becomes enormous.